import functools

# 三维DP
# class Solution(object):
#     def countPalindromicSubsequences(self, s):
#         n = len(s)
#         base = 10 ** 9 + 7
#
#         @functools.cache
#         def dfs(c, i, j):
#             if i > j:
#                 return 0
#             if i == j:
#                 if s[i] == c:
#                     return 1
#                 else:
#                     return 0
#             if s[i] == c:
#                 if s[j] == c:
#                     return (2 + dfs('a', i + 1, j - 1) + dfs('b', i + 1, j - 1) + dfs('c', i + 1, j - 1) + dfs('d', i + 1, j - 1)) % base
#                 else:
#                     return dfs(c, i, j - 1)
#             else:
#                 if s[j] == c:
#                     return dfs(c, i + 1, j)
#                 else:
#                     return dfs(c, i + 1, j - 1)
#
#         return (dfs('a', 0, n - 1) + dfs('b', 0, n - 1) + dfs('c', 0, n - 1) + dfs('d', 0, n - 1)) % base

# 二维DP
import collections


class Solution(object):
    def countPalindromicSubsequences(self, s):
        base = 10 ** 9 + 7
        n = len(s)
        d = collections.defaultdict(list)
        next_p = [-1] * n
        pre_p = [-1] * n
        for index, c in enumerate(s):
            d[c].append(index)
        for c in d:
            for i in range(len(d[c]) - 1):
                next_p[d[c][i]] = d[c][i + 1]
            for i in range(len(d[c]) - 1, 0, -1):
                pre_p[d[c][i]] = d[c][i - 1]

        @functools.cache
        def dfs(i, j):
            if i == j:
                return 1
            if i > j:
                return 0
            if s[i] == s[j]:
                low = next_p[i]
                high = pre_p[j]
                if low > high:
                    return (2 + dfs(i + 1, j - 1) * 2) % base
                if low == high:
                    return (dfs(i + 1, j - 1) * 2 + 1) % base
                if low < high:
                    return (2 * dfs(i + 1, j - 1) - dfs(low + 1, high - 1)) % base
            else:
                return (dfs(i + 1, j) + dfs(i, j - 1) - dfs(i + 1, j - 1)) % base

        return dfs(0, n - 1)


data = Solution()
s = 'bccb'
print(data.countPalindromicSubsequences(s))
s = 'abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba'
print(data.countPalindromicSubsequences(s))
